function G = slgraph(nnodes, edges, varargin)
%SLGRAPH Constructs a graph/bigraph given the number of nodes and the edge set
%
% [ Syntax ]
%   - G = slgraph(n, edges, ...);
%   - G = slgraph([ns, nt], edges, ...);
%
% [ Arguments ]
%   - n:        the number of nodes in the graph
%   - ns:       the number of source nodes in the bi-graph
%   - nt:       the number of targte nodes in the bi-graph
%   - edges:    the edge set. It can be given in two forms:
%                - Suppose there are ne edges, then it can be
%                  input as an ne x 2 array, each row gives the
%                  indices of the source and target node indices
%                  of the corresponding edge. If the i-th row is
%                  [v1 v2], then the i-th edge is from the v1-th 
%                  node to the v2-th node. 
%                - The edges can also be given in form of an
%                  ne x 3 array. The 3rd column specifies the 
%                  values associated with the corresponding edges.
%   - G:        the constructed graph
%               
% [ Description ]
%   - G = slgraph(n, edges, ...) constructs a graph with n nodes. 
%     G will be an n x n matrix (or sparse matrix). G(i, j) is the
%     value associated with the edge connecting from i-th node to
%     j-th node.
%
%     When the edges has three columns, the values in the third column
%     are used as the values associated with the corresponding edge.
%     When the edges has two columns, if property vfun is specified, the 
%     values associated with each edge is produced by vfun. otherwise,
%     the value associated with each edge is set to one.
%
%     You can specify the following properties to further specify
%     how the graph is constructed.
%     \{:
%         - vfun:           the function handle to evaluate the values 
%                           associated with the edges. The syntax is
%                               $ v = vfun(s, t) $
%                           s is a column vector of source node indices, t 
%                           is a column vector of target node indices. It 
%                           should output a column vector of the same size 
%                           or a scalar. 
%                           vfun can also be a scalar value, which will be 
%                           set to all edges.
%
%         - mval_handle:    the strategy to handle the case when the same
%                           edge occurs multiple times.
%                           It can be either of the following strings:
%                            \{:
%                               - sum:      sum up the values of each
%                                           occurrence as the value of 
%                                           the edge
%                               - max:      select the maximum value as
%                                           the value of the edge
%                               - min:      select the minimum value as the
%                                           value of the edge
%                               - mean:     set the value of the edge to
%                                           be the average of the values
%                                           of all its occurrence.   
%                               - first:    set the value of the edge to
%                                           the first occurred value
%                               - last:     set the value of the edge to 
%                                           the last occurred value
%                            \:}
%                           The mval_handle can also be a function handle
%                           with the following syntax:
%                               $ v = h(x) $
%                           x is the vector of all occurred values associated 
%                           to the edge. v is the final value associated with 
%                           the edge.
%
%                           By default, mval_handle is set to empty, then no
%                           handling of multiple occurrences of the same
%                           edge will be performed. In this case, only the 
%                           last occurred value for an edge will take
%                           effect. It is functionally equivalent to
%                           'last'.
%
%         - output:         the form of output matrix. It can be either
%                           'full' or 'sparse'. Default is 'sparse'.
%     \:}
%
%   - G = slgraph([ns, nt], edges, ...) constructs a bi-graph with ns source nodes
%     and nt target nodes. G will be an ns x nt matrix (or sparse matrix).
%     G(i, j) is the value associated with the edge connecting from the
%     i-th source node to the j-th target node. 
%     
%     The aforementioned properties also apply to the construction of
%     bi-graph.
%
% [ Examples ]
%   - Construct a graph with 4 nodes, with 5 edges (1, 2), (1, 3), (2, 4),
%     (4, 5), and (5, 2).
%     \{
%         G = slgraph(4, [1 2; 1 3; 2 4; 4 3; 3 2]);
%     \}
%
%   - Construct a symmetric graph with 4 nodes. with the edges connecting 
%     1 and 4, 2 and 3, 3 and 3.
%     \{
%         G = slgraph(4, [1 4; 4 1; 2 3; 3 2; 3 3]);
%     \}
%     You can see that, you need to specify both (i1, i2) and (i2, i1) when
%     you set a bi-directional edge if i1 is not equal to i2.
%     
%     However, if you don't want to specify each edge twice, you can first
%     construct an asymmetric graph using slgraph, and then invoke
%     slsymgraph to make it symmetric.
%
%   - Construct a graph with 3 nodes, and the edge values are explicitly 
%     specified. The output adjacency matrix is required to be a full
%     matrix.
%     \{
%         G = slgraph(3, [2 2 0.8; 1 2 0.2; 1 3 0.4; 3 1 0.5], 'output', 'full');
%
%         G <= [0     0.2   0.4
%               0     0.8   0
%               0.5   0     0   ]
%     \}
%
%   - Construct a graph with 3 nodes, each node is associated with a column
%     in the matrix X. The edge values are computed as cityblock distance 
%     between the vectors corresponding to the nodes that links.
%     \{
%         X = [1 3 6
%              4 5 7];
%         G = slgraph(3, [1 2; 1 3; 2 3; 3 2], ...
%                     'vfun', @(i, j) sum(abs(X(:,i) - X(:,j)), 1)',
%                     'output', 'full')
%         
%         G <= [0  3  8
%               0  0  5
%               0  5  0]
%     \}
%
%   - Construct a graph with 3 nodes. The value associated with each
%     existing edge is set to a user-input number, say 3. 
%     \{
%         u = 3;
%         G = slgraph(3, [1 2; 1 3; 2 3; 3 2], ...
%                     'vfun', @(i,j) u, 'output', 'full')
%         
%         G <= [0  3  3
%               0  0  3
%               0  3  0]           
%     \}
%
%   - Construct a graph for which multiple edges connecting the same source
%     and target nodes can be specified. In the final graph, the edge
%     connecting these source and target nodes are the sum of the all
%     corresponding values specified in the input.
%     \{
%         G = slgraph(3, [1 1 0.1; 1 2 0.1; 1 3 0.2; 1 2 0.2; 2 1 0.1], ...
%                     'mval_handle', 'sum', 'output', 'full')
%       
%         G <= [0.1 0.3 0.2
%               0.1 0   0
%               0   0   0   ]
%     \}
%     If the values are not explicitly specified by the 3rd column, then the
%     values for each edge is the counting of its occurrences in the input
%     array.
%     \{
%         G = slgraph(3, [1 1; 1 2; 1 3; 1 2; 2 1], ...
%                     'mval_handle', 'sum', 'output', 'full')
%
%         G <= [1 2 1
%               1 0 0
%               0 0 0 ];
%     \}
%
%   - You can also use other ways to handle the case of multiple
%     occurrences.
%     \{
%         G = slgraph(3, [1 1 0.1; 1 2 0.4; 1 3 0.2; 1 2 0.7; 2 1 0.3], ...
%                     'mval_handle', 'max', 'output', 'full')
%
%         G <= [0.1  0.7  0.2
%               0.3  0    0
%               0    0    0   ]
%     \}
%     You can also define your own handler as a function handle
%     \{
%         G = slgraph(3, [1 1 0.1; 1 2 0.4; 1 3 0.2; 1 2 0.7; 2 1 0.3], ...
%                     'mval_handle', @(x) 0.2*max(x)+0.8*min(x), 'output', 'full')
%
%         G <= [0.1  0.46  0.2
%               0.3  0     0
%               0    0     0   ]
%     \}
%
%   - Construct a bigraph with 3 source nodes and 4 target nodes
%     \{
%         G = slgraph([3 4], [1 2; 1 4; 2 3; 2 4; 3 1]);
%     \}
%
% [ History ]
%   - Created by Dahua Lin, on Jul 4, 2007
%

%% parse and verify input 

error(nargchk(2, inf, nargin));
[gsiz, E, vals, vfun, mvh, out_sparse] = parse_options(nnodes, edges, varargin{:});


%% get edge values

ne = length(E);
if isempty(vals)
    if isempty(vfun)
        vals = ones(ne, 1);
    else
        vals = zeros(ne, 1);
        vals(:) = vfun(edges(:,1), edges(:,2));
    end
end

if ~isempty(mvh)
    [E, vals] = slprefilter_edges(E, vals, mvh);
end


%% construct the graph

if out_sparse
    G = spalloc(gsiz(1), gsiz(2), length(E));
else
    G = zeros(gsiz);
end

G(E) = vals;



%% The function to parse input arguments

function [gsiz, E, vals, vfun, mvh, out_sparse] = parse_options(nnodes, edges, varargin)

if ~isnumeric(nnodes) || numel(nnodes) > 2
    error('sltoolbox:slgraph:invalidarg', ...
        'The first argument of slgraph should be a scalar or a length-2 vector');
end
if isscalar(nnodes)
    gsiz = [nnodes, nnodes];
else
    gsiz = nnodes(:)';
end

if isnumeric(edges) && ndims(edges) == 2    
    ed_n = size(edges, 2);
    if ed_n == 2        
        vals = [];
    elseif ed_n == 3
        vals = edges(:, 3);
    else
        error('sltoolbox:slgraph:invalidarg', ...
            'The edges should be either a n x 2 or n x 3 matrix.');
    end
    E = sub2ind(gsiz, edges(:,1), edges(:,2));
else
    error('sltoolbox:slgraph:invalidarg', ...
        'The edges should be either a n x 2 or n x 3 matrix.');
end

opts = struct( ...
    'vfun', [], ...
    'mval_handle', [], ...
    'output', 'sparse');
opts = setopts(opts, varargin{:});

vfun = opts.vfun;

if ischar(opts.mval_handle)
    switch opts.mval_handle
        case 'sum'
            mvh = @sum;
        case 'max'
            mvh = @max;
        case 'min'
            mvh = @min;
        case 'mean'
            mvh = @(x) sum(x) / numel(x);
        case 'first'
            mvh = @(x) x(1);
        case 'last'
            mvh = @(x) x(end);
        otherwise
            error('sltoolbox:slgraph:invalidopt', ...
                'Unknown multi-val handler: %s', opts.mval_handle);
    end
elseif isa(opts.mval_handle, 'function_handle');
    mvh = opts.mval_handle;
elseif isempty(opts.mval_handle)
    mvh = [];
else
    error('sltoolbox:slgraph:invalidarg', ...
        'The multi-val handler should be a string, a function handle, or empty');
end

if ischar(opts.output)
    switch opts.output
        case 'sparse'
            out_sparse = true;
        case 'full'
            out_sparse = false;        
        otherwise
            error('sltoolbox:slgraph:invalidopt', ...
                'Unknown output option: %s', opts.output);
    end
else
    error('sltoolbox:slgraph:invalidarg', ...
        'The output option should be a string');
end
    
